package Leetcode;

import java.util.*;
import java.util.stream.Collectors;

/**
 * 有效 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 '.' 分隔。
 * <p>
 * 例如："0.1.2.201" 和 "192.168.1.1" 是 有效 IP 地址，但是 "0.011.255.245"、"192.168.1.312" 和 "192.168@1.1" 是 无效 IP 地址。
 * 给定一个只包含数字的字符串 s ，用以表示一个 IP 地址，返回所有可能的有效 IP 地址，这些地址可以通过在 s 中插入 '.' 来形成。
 * 你 不能 重新排序或删除 s 中的任何数字。你可以按 任何 顺序返回答案。
 * <p>
 * 示例 1：
 * 输入：s = "25525511135"
 * 输出：["255.255.11.135","255.255.111.35"]
 * <p>
 * 示例 2：
 * 输入：s = "0000"
 * 输出：["0.0.0.0"]
 * <p>
 * 示例 3：
 * 输入：s = "101023"
 * 输出：["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]
 * <p>
 * 提示：
 * 1 <= s.length <= 20
 * s 仅由数字组成
 */
public class 力扣93_复原IP地址 {

    public ArrayList<String> restoreIpAddresses(String s) {
        ArrayList<String> res = new ArrayList<>();
        Integer[] segments = new Integer[4];
        dfs(s, 0, 0, res, segments);
        return res;
    }

    public void dfs(String s, int currentId, int curSegment, List<String> res, Integer[] segments) {
        // 满足条件，到达第四段+1，并且字符串遍历到最后length+1，说明刚好满足条件，需要存下来
        // ! 需要注意是 +1，因为满足条件后，又再次调用了dfs(i + 1, curSegment + 1)
        if (currentId == s.length() && curSegment == 4) {
            String join = Arrays.stream(segments).map(Object::toString).collect(Collectors.joining("."));
            res.add(join);
            return;
        }

        // ! 终止条件，字符已经遍历结束了，已经到达第4段，下面就会越界
        if (currentId >= s.length() || curSegment >= 4) {
            return;
        }

        // 特殊处理，如果当前位置字符为0，直接设置为0，进入下次循环，因为不可能以0开头
        if (s.charAt(currentId) == '0') {
            segments[currentId] = 0;
            dfs(s, currentId + 1, curSegment + 1, res, segments);
            return;
        }

        // 二叉树 第h层的节点个数最多为2^(h-1)个，最多有(2^h)-1个节点
        // 回溯，到这里分支，进行动态探测，走遍所有的可能，最多分3支
        // 时间复杂度，由于 IP 地址的每一段的位数不会超过 3，因此在递归的每一层，我们最多只会深入到下一层的 3 种情况。
        // 又因为我们的IP总段数为 4，所以递归最大深度为 4。
        // 算法模型类似与一个三叉树，深度为4。所以时间复杂度就是树的节点数(3^h)-1，将常量1去掉，为O(3^4)。
        // 因为每次，还需要将找到的结果加入答案数组，所以总的时间复杂度为O(3^4 * s)
        int roundNum = 0;
        for (int i = currentId; i < s.length(); i++) {
            roundNum = roundNum * 10 + s.charAt(i) - '0';
            if (roundNum <= 255) {
                segments[curSegment] = roundNum;
                dfs(s, i + 1, curSegment + 1, res, segments);
                // 不需要移除上边添加的数据，因为下次会覆盖数组内的数据
//                segments[curSegment] = 0;
            } else {
                break;
            }
        }
    }

    public static void main(String[] args) {
        力扣93_复原IP地址 main = new 力扣93_复原IP地址();
        System.out.println(main.restoreIpAddresses("25525511135"));
        System.out.println(main.restoreIpAddresses("0000"));
        System.out.println(main.restoreIpAddresses("101023"));
    }
}
